# -*- coding: utf-8 -*-
# @Time    : 2019-09-11 15:57
# @Author  : Jaedong
# @Version : 3.6
# @File    : TryFill.py
# @Software: PyCharm

import time

# 尝试去解数独
def try_fill(grid):
    start_time = time.time()

    # 破解数独的过
    solve(grid)

    end_time = time.time()
    print("总共消耗的时间为：{}".format(end_time - start_time))
    return grid

# 真正解决数独的暴力方法
def solve(grid):
    canuse_array = [[[] for n in range(9)] for n in range(9)]
    for row in range(9):
        for column in range(9):
            if grid[row][column] == 0:  # 如果单元格内的数字为0，也就是尚未填充数字，就对其可能填充的数字集合进行试探性填充
                existed_set = {0}
                for index in range(9):  # 查看所在行列
                    existed_set.add(grid[row][index])  # 将待填充单元格的所在行的所有已经填充的数字加入集合
                    existed_set.add(grid[index][column])  # 将待填充单元格所在列的所有已填充的数字加入集合

                for i in range(3):  # 查看所在九宫格
                    for j in range(3):
                        existed_set.add(grid[row // 3 * 3 + i][column // 3 * 3 + j])  # 将单元格所在九宫格中的数字都写进已填写集合

                if len(existed_set) != 10:  # 如果该单元格所在的行列以及九宫格内的已填充数字包含10个(0-9)，证明不需要填充
                    for canUse in range(1, 10):  # 查漏补缺，如果1-9这9个数字中有可以填充入单元格的，就进行填充去试
                        if canUse not in existed_set:
                            canuse_array[row][column].append(canUse)
            else:
                canuse_array[row][column].append(grid[row][column])

    for row in range(9):
        for colunm in range(9):
            # 找到canuse_array中的第一个可能性不为1个的位置
            if grid[row][colunm] == 0:
                for case in canuse_array[row][colunm]:
                    grid[row][colunm] = case
                    if solve(grid):
                        return True
                grid[row][colunm] = 0
                return False
    return True